package 动态规划.经典动态规划题目.鸡蛋掉落;

import java.util.Arrays;

public class 鸡蛋掉落_887 {
    public static void main(String[] args) {
        System.out.println(new 鸡蛋掉落_887().superEggDrop(2, 6));
    }

    /**
     * 进阶方法：使用二分搜索优化
     *
     * @param K
     * @param N
     * @return
     */
    public int superEggDrop(int K, int N) {
        int[][] memo = new int[K + 1][N + 1];
        for (int[] item : memo) {//初始化一下备忘录，方便判定一下res是否存在于备忘录中
            Arrays.fill(item, -1);
        }
        return dp(K, N, memo);
    }

    public int dp(int K, int N, int[][] memo) {

        //base case
        if (K == 1) {//只有一个鸡蛋，只能线性扫描所有楼层
            return N;
        }
        if (N == 0) {//楼层为0，不需要扔鸡蛋
            return 0;
        }

        if (memo[K][N] != -1) {//备忘录有记录
            return memo[K][N];
        }

        int res = Integer.MAX_VALUE;
        int lo = 1;
        int hi = N;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int broken = dp(K - 1, mid - 1, memo);//鸡蛋碎了
            int not_broken = dp(K, N - mid, memo);//鸡蛋没碎

            //res=min(max(碎,没碎)+1);被分解成了下面两个 res
            if (broken > not_broken) {//没碎的函数在碎了的函数之上
                hi = mid - 1;//要靠近两函数交点，必须要缩小hi
                res = Math.min(res, broken + 1);//+1是因为在当前楼层扔鸡蛋，所以也要加一次次数
            } else {//碎的函数在没碎的函数之上
                lo = mid + 1;//要靠近两函数交点，必须要增大lo
                res = Math.min(res, not_broken + 1);
            }
        }
        memo[K][N] = res;
        return res;
    }


    /**
     * 用这种方法在K:6 N:5000的时候会超出时间限制，需要优化
     * @param K
     * @param N
     * @return
     */
//    public int superEggDrop(int K, int N) {
//        int[][] memo = new int[K + 1][N + 1];
//        for (int[] item : memo) {//初始化一下备忘录，方便判定一下res是否存在于备忘录中
//            Arrays.fill(item, -1);
//        }
//        return dp(K, N, memo);
//    }
//
//    public int dp(int K, int N, int[][] memo) {
//
//        //base case
//        if (K == 1) {//只有一个鸡蛋，只能线性扫描所有楼层
//            return N;
//        }
//        if (N == 0) {//楼层为0，不需要扔鸡蛋
//            return 0;
//        }
//
//        if (memo[K][N] != -1) {//备忘录有记录
//            return memo[K][N];
//        }
//
//        int res = Integer.MAX_VALUE;
//        for (int i = 1; i <= N; i++) {//i代表楼层
//            res = Math.min(res, Math.max(dp(K - 1, i - 1, memo), dp(K, N - i, memo)) + 1);
//        }
//        memo[K][N] = res;
//        return res;
//    }
}
